/**
 *
 * 以力扣 “岛屿数量” 这道题为例，编写 UnionFind
 *
 * 并查集本质上是一片森林，每个集合即为一颗树。
 *
 * 有两个基本操作：
 *  - [1] 查找元素所在的集合，返回这个集合的“代表元素”，即根节点
 *  - [2] 合并两个集合
 *
 * 注意：
 *  [1]查找的过程可以压缩路径
 *  [2]合并的时候，可以将高度小的树合并到高度大的（因此维护了height数组）
 *
 */

#include <vector>
#include <unordered_set>

using namespace std;

class UnionFind
{
private:
    vector<int> parent;
    vector<int> height;

public:
    UnionFind(int size): parent(size), height(size, 1)
    {
        // 初始化：每个节点单独成一个集合, 高度都为 1
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
        }
    }
    // 查找元素 x 所在集合的代表元素(根)
    int find(int x)
    {
        if (parent[x] != x) {
            // 递归继续向上查找
            // 另外, 将集合内的节点都连接到根节点下
            // 以降低树的高度。
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y)
    {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx == rooty) {
            return;
        }

        if (height[rootx] < height[rooty]) {
            parent[rootx] = rooty;
        } else if (height[rootx] > height[rooty]) {
            parent[rooty] = rootx;
        } else {
            parent[rooty] = rootx;
            height[rootx] += 1;
        }
    }
};

class Solution
{
public:
    int numIslands(vector<vector<char> >& grid)
    {
        int m = grid.size();
        int n = grid[0].size();

        UnionFind uf(m * n); // 初始化并查集，每个格子一个节点

        // 将矩阵坐标 (i, j) 转换成并查集的下标 index
        auto index = [&](int i, int j) -> int {
            return i * n + j;
        };

        // 1.合并所有相邻陆地到并查集
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] != '1') {
                    continue;
                }
                // 当前元素合并到上面的一个元素
                if (i > 0 && grid[i - 1][j] == '1') {
                    uf.unionSets(index(i, j), index(i - 1, j));
                }
                // 当前元素合并到左边的一个元素
                if (j > 0 && grid[i][j - 1] == '1') {
                    uf.unionSets(index(i, j), index(i, j - 1));
                }
            }
        }

        // 2.在并查集中查找有多少个独立的集合(通过unordered_set去重)
        unordered_set<int> uniqueIslands;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    uniqueIslands.insert(uf.find(index(i, j)));
                }
            }
        }

        return uniqueIslands.size();
    }
};

int main()
{
    return 0;
}